// https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
// Created by ade on 2022/7/20.
//给你二叉树的根结点 root ，请你将它展开为一个单链表：
//
//展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
//展开后的单链表应该与二叉树 先序遍历 顺序相同。
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 如果节点存在左子树，将节点的右子树接到左子树的最右端节点，并将左子树变成右子树，
    // 如果节点不存在左子树，则跳过该节点继续处理；
    void flatten(TreeNode *root) {
        TreeNode *cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode *p = cur->left;
                while (p->right) p = p->right;
                p->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }

    TreeNode *init() {
        // [1,2,2,3,3,null,null,4,4]
        TreeNode *head1 = new TreeNode(1);
        TreeNode *head2 = new TreeNode(2);
        TreeNode *head3 = new TreeNode(2);
        TreeNode *head4 = new TreeNode(3);
        TreeNode *head5 = new TreeNode(3);
        TreeNode *head6 = new TreeNode(4);
        TreeNode *head7 = new TreeNode(4);
        head1->left = head2;
        head1->right = head3;
        head2->left = head4;
        head2->right = head4;
        head3->left = nullptr;
        head3->right = nullptr;
        head4->left = head6;
        head4->right = head6;
        return head1;
    }

    void show(TreeNode *node) {
        if (!node) return;
        cout << node->val << ",";
        show(node->left);
        show(node->right);
    }
};

int main() {
    Solution so;
    TreeNode *head = so.init();
    so.flatten(head);
    so.show(head);
//    cout << head->val << endl;
    return 0;
}
